home *** CD-ROM | disk | FTP | other *** search
/ Mac Power 1997 December / MACPOWER-1997-12.ISO.7z / MACPOWER-1997-12.ISO / AMUG / PROGRAMMING / Raven 1.2.sit / Raven 1.2 / • Extras • / SGI STL / stack.h < prev    next >
C/C++ Source or Header  |  1997-05-28  |  6KB  |  188 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  *
  15.  * Copyright (c) 1996
  16.  * Silicon Graphics Computer Systems, Inc.
  17.  *
  18.  * Permission to use, copy, modify, distribute and sell this software
  19.  * and its documentation for any purpose is hereby granted without fee,
  20.  * provided that the above copyright notice appear in all copies and
  21.  * that both that copyright notice and this permission notice appear
  22.  * in supporting documentation.  Silicon Graphics makes no
  23.  * representations about the suitability of this software for any
  24.  * purpose.  It is provided "as is" without express or implied warranty.
  25.  *
  26.  * Copyright (c) 1997
  27.  * Moscow Center for SPARC Technology
  28.  *
  29.  * Permission to use, copy, modify, distribute and sell this software
  30.  * and its documentation for any purpose is hereby granted without fee,
  31.  * provided that the above copyright notice appear in all copies and
  32.  * that both that copyright notice and this permission notice appear
  33.  * in supporting documentation.  Moscow Center for SPARC Technology makes no
  34.  * representations about the suitability of this software for any
  35.  * purpose.  It is provided "as is" without express or implied warranty.
  36.  *
  37.  */
  38.  
  39.  
  40. #ifndef __SGI_STL_STACK_H
  41. #define __SGI_STL_STACK_H
  42.  
  43. # ifndef __SGI_STL_FUNCTION_H
  44. #  include <function.h>
  45. # endif
  46. # ifndef __SGI_STL_HEAP_H
  47. #  include <heap.h>
  48. # endif
  49. # ifndef __SGI_STL_VECTOR_H
  50. #  include <vector.h>
  51. # endif
  52. # ifndef __SGI_STL_DEQUE_H
  53. #  include <deque.h>
  54. # endif
  55.  
  56. __BEGIN_STL_NAMESPACE
  57.  
  58. template <class T, __DFL_TMPL_PARAM(Sequence,vector<T>) >
  59. class stack {
  60. friend bool operator==(const stack<T, Sequence>& x, const stack<T, Sequence>& y);
  61. friend bool operator<(const stack<T, Sequence>& x, const stack<T, Sequence>& y);
  62. public:
  63.     typedef typename Sequence::value_type value_type;
  64.     typedef typename Sequence::size_type size_type;
  65. protected:
  66.     Sequence c;
  67. public:
  68.     bool empty() const { return c.empty(); }
  69.     size_type size() const { return c.size(); }
  70.     value_type& top() { return c.back(); }
  71.     const value_type& top() const { return c.back(); }
  72.     void push(const value_type& x) { c.push_back(x); }
  73.     void pop() { c.pop_back(); }
  74. };
  75.  
  76. template <class T, class Sequence>
  77. bool operator==(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
  78.     return x.c == y.c;
  79. }
  80.  
  81. template <class T, class Sequence>
  82. bool operator<(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
  83.     return x.c < y.c;
  84. }
  85.  
  86.  
  87. template <class T, __DFL_TMPL_PARAM(Sequence,deque<T>) >
  88. class queue {
  89. friend bool operator==(const queue<T, Sequence>& x, const queue<T, Sequence>& y);
  90. friend bool operator<(const queue<T, Sequence>& x, const queue<T, Sequence>& y);
  91. public:
  92.     typedef typename Sequence::value_type value_type;
  93.     typedef typename Sequence::size_type size_type;
  94. protected:
  95.     Sequence c;
  96. public:
  97.     bool empty() const { return c.empty(); }
  98.     size_type size() const { return c.size(); }
  99.     value_type& front() { return c.front(); }
  100.     const value_type& front() const { return c.front(); }
  101.     value_type& back() { return c.back(); }
  102.     const value_type& back() const { return c.back(); }
  103.     void push(const value_type& x) { c.push_back(x); }
  104.     void pop() { c.pop_front(); }
  105. };
  106.  
  107. template <class T, class Sequence>
  108. bool operator==(const queue<T, Sequence>& x, const queue<T, Sequence>& y) {
  109.     return x.c == y.c;
  110. }
  111.  
  112. template <class T, class Sequence>
  113. bool operator<(const queue<T, Sequence>& x, const queue<T, Sequence>& y) {
  114.     return x.c < y.c;
  115. }
  116.  
  117. template <class T, __DFL_TMPL_PARAM(Sequence,vector<T>), 
  118.           __DFL_TMPL_PARAM(Compare,less<typename Sequence::value_type>) >
  119. class  priority_queue {
  120. public:
  121.     typedef typename Sequence::value_type value_type;
  122.     typedef typename Sequence::size_type size_type;
  123. protected:
  124.     Sequence c;
  125.     Compare comp;
  126. public:
  127.     priority_queue() :  c(), comp(Compare()) {}
  128.     explicit priority_queue(const Compare& x) :  c(), comp(x) {}
  129.     priority_queue(const value_type* first, const value_type* last, 
  130.            const Compare& x = Compare()) : c(first, last), comp(x) {
  131.     make_heap(c.begin(), c.end(), comp);
  132.     }
  133. /*
  134.     template <class InputIterator>
  135.     priority_queue(InputIterator first, InputIterator last, 
  136.            const Compare& x = Compare()) : c(first, last), comp(x) {
  137.     make_heap(c.begin(), c.end(), comp);
  138.     }
  139. */
  140.     bool empty() const { return c.empty(); }
  141.     size_type size() const { return c.size(); }
  142.     const value_type& top() const { return c.front(); }
  143.     void push(const value_type& x) { 
  144.     c.push_back(x); 
  145.     push_heap(c.begin(), c.end(), comp);
  146.     }
  147.     void pop() { 
  148.     pop_heap(c.begin(), c.end(), comp);
  149.     c.pop_back(); 
  150.     }
  151. };
  152.  
  153. // no equality is provided
  154.  
  155. #if defined  (__STL_DEFAULT_TEMPLATE_PARAM)
  156. #  define simple_stack stack
  157. #  define simple_queue queue
  158. #  define simple_priority_queue priority_queue
  159. # else
  160. // provide ways to access short funclionality
  161.  
  162. // provide a "default" stack adaptor
  163. template <class T>
  164. class simple_stack : public stack<T, vector<T> > 
  165. {
  166. };
  167.  
  168. // provide a "default" queue adaptor
  169. template <class T>
  170. class simple_queue : public queue<T, deque<T> > 
  171. {
  172. };
  173.  
  174. // provide a "simple" priority queue adaptor
  175. template <class T>
  176. class simple_priority_queue : public priority_queue<T, deque<T> , less<T> > 
  177. {
  178.     simple_priority_queue() : priority_queue() {}
  179.     simple_priority_queue(const value_type* first, const value_type* last) : 
  180.          priority_queue(first,last){}
  181. };
  182.  
  183. #endif /* __STL_DEFAULT_TEMPLATE_PARAM */
  184.  
  185. __END_STL_NAMESPACE
  186.  
  187. #endif
  188.